package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.util.Arrays;

/**
 * 球和篮子的问题
 */
public class qiuAndLanZi {
	/**
	 * 你有几个同样的球，你希望把它放到几个篮子里。每个篮子有相同的容量。给出int 型的baskets,代表篮子的数量。
	 * 给出int型的 capacity，代表每个篮子的最大容量。给出int型的balls,表示归类到篮子里的球的数量。
	 * 返回值是把球归类到篮子里的方式的数量。如果不能完全存放到篮子中，无法划分，返回0。
	 * 篮子互不同，所有的球相同。因此，如果2个球放到2个篮子里，你可以采用3种方式，即(0, 2), (1, 1), 或 (2, 0)
	 */
	int count = 0;
	public int countWays(int lanzinum,int lanzisize,int qiunum){
		//size为循环的结束点
		int size = lanzisize > qiunum ? qiunum : lanzisize;
		return count(lanzinum,size,qiunum,new int[lanzinum],1);
	}
	
	public int count(int lanzinum,int size,int qiunum,int[] cache,int ceng){
		for (int a = 0 ; a <= size ; a++) {
			cache[ceng - 1] = a;
			if (ceng == lanzinum && sum(cache) == qiunum) {
				print(cache);
				count ++;
			}
			if (ceng < lanzinum) {
				count(lanzinum,size,qiunum,cache,ceng + 1);
			}
		}
		return count;
	}
	
	public void print(int[] cache){
		Arrays.stream(cache).forEach(a -> System.out.print(a + " "));
		System.out.println();
	}
	
	public int sum(int[] cache){
		return Arrays.stream(cache).sum();
	}
	
	@Test
	public void test(){
		int lanzinum = 3;
		int lanzisize = 2;
		int qiunum = 2;
		int i = countWays(lanzinum, lanzisize, qiunum);
		System.out.println(i);
	}
}

class FillBaskets {
	int count=0;
	//baskets篮子的数量。capacity每个篮子的最大容量。balls归类到篮子里的球的数量
	int baskets,capacity,balls;
	int[] bas;
	
	public static void main(String[] args) {
		int i = new FillBaskets().countWays(3, 2, 2);
		System.out.println(i);
	}
	
	public int countWays(int baskets, int capacity, int balls) {
		if (baskets*capacity<balls)
			return 0;
		this.baskets=baskets;
		this.balls=balls;
		if (balls<capacity)
			capacity=balls;
		this.capacity=capacity;
		bas=new int[baskets];
		
		//从第0个篮子开始放
		putBalls(0);
		return count;
	}
	
	//
	void putBalls(int n) {
		
		//检测是不是到达最后篮子
		if (n==baskets) {
			if (getSumBalls()==balls)
				count++;
			return;
		}
		
		//给第n个篮子放球,并且从0->capacity
		//一次轮循的放入
		for (int i=0;i<=capacity;i++) {
			bas[n]=i;
			putBalls(n+1);
		}
	}
	//得到当前篮子里面所有的球
	int getSumBalls() {
		int sum=0;
		for (int i=0;i<baskets;i++)
			sum+=bas[i];
		return sum;
	}
}
